iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 2
0
Software Development

天天 LeetCode,立地成佛:三十天從頭開始學演算法系列 第 2

[Day 2] Two Sum:暴力解不難,但善用 dictionary 讓你更輕鬆

  • 分享至 

  • xImage
  •  

講到 LeetCode,大部分人共同的回憶(以及共同的起點)大概就是 two Sum 了吧。這題會給一個陣列以及一個數字,我們要找的,就是陣列中哪兩個數字加起來剛好等於目標。雖然看起來不是很難,但新手剛碰時還是可能因為各種東西卡關,我第一次解就卡了很久QQ

其實這題暴力解也沒問題,只要用 for 迴圈或 while 慢慢兩個兩個加總並對照,就可以找到答案,但是想當然效率不會太好。換個角度思考,加法的反面就是減法,我們可以把兩個數字加起來跟目標數對照,也可以用目標數減掉正在瀏覽的陣列元素,然後拿這個得到的數字去和剩下的元素比較,看裡面有沒有我們要的。

不過,如果拿數字慢慢去比較的話,我們還是要跑一樣的迴圈數量。因此,這時候 dictionary 就上場了。dictionary 的元素是 (key, value) 的配對,在提取元素的時候,把 key 丟進去就能拿到,相較於無法直接判斷某元素是否在裡面的 array 會方便一些。所以,我們可以把目標減掉陣列元素後的數值丟到 dictionary 裡面,然後繼續往下瀏覽,如果之後的元素剛好能在 dictionary 裡面,就找到答案啦。

下面附上題目和簡單的程式碼分享,有問題或建議也歡迎留言,謝謝大家~

https://ithelp.ithome.com.tw/upload/images/20200909/20129662hta2dr2zK6.png

// javascript

const twoSum = function(nums, target) {
    const dicy = {};
    for(let i=0; i<nums.length; i++){
        if(dict[nums[i]] >= 0){
            return [ dict[nums[i]] , i]
        }
        dict[target-nums[i]] = i
    }
};
其實本來想要寫別的可是卡住了解不完QQ

上一篇
[Day 1] 不是在摸魚,但認識環境真的很重要
下一篇
[Day 3] Sort an Array:大事化小小事化無的解決法,Divide and Conquer
系列文
天天 LeetCode,立地成佛:三十天從頭開始學演算法12
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言